package greedy.总结.基础;

import java.util.Arrays;
import java.util.PriorityQueue;

public class leetcode1029两地调度 {

    public int twoCitySchedCost(int[][] costs) {
        Arrays.sort(costs, (o1, o2) -> Math.abs(o2[0] - o2[1]) - Math.abs(o1[0] - o1[1]));
        int length = costs.length;
        int left = 0;
        int right = 0;
        int sum = 0;
        for (int i = 0; i < length; i++) {
            if (costs[i][0] < costs[i][1]) {
                if (left < length / 2) {
                    left++;
                    sum += costs[i][0];
                } else {
                    right++;
                    sum += costs[i][1];
                }
            } else {
                if (right < length / 2) {
                    right++;
                    sum += costs[i][1];
                } else {
                    left++;
                    sum += costs[i][0];
                }
            }
        }
        return sum;
    }

    // 评论区优选
    // 机会成本
    public int twoCitySchedCost1(int[][] costs) {

        //首先假设全部去A市，再从其中找出去b市比较便宜的n个
        int ret = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int[] i : costs){
            ret += i[0];
            pq.add(i[1] - i[0]);
        }

        for (int i = 0; i < costs.length / 2 ; i++) {
            ret += pq.poll();
        }
        return ret;
    }
}
